{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Wording Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #two-pointers #string #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #双指针 #字符串 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canAliceWin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 分别拥有一个&nbsp;<strong>按字典序排序&nbsp;</strong>的字符串数组，分别命名为 <code>a</code>&nbsp;和 <code>b</code>。</p>\n",
    "\n",
    "<p>他们正在玩一个单词游戏，遵循以下规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每一轮，当前玩家应该从他的列表中选择一个单词，并且选择的单词比上一个单词 <strong>严格大</strong>；然后轮到另一名玩家。</li>\n",
    "\t<li>如果一名玩家在自己的回合中无法选择单词，则输掉比赛。</li>\n",
    "</ul>\n",
    "\n",
    "<p>Alice 通过选择在 <strong>字典序最小</strong> 的单词开始游戏。</p>\n",
    "\n",
    "<p>给定 <code>a</code> 和 <code>b</code>，已知两名玩家都按最佳策略玩游戏，如果 Alice 可以获胜，则返回 <code>true</code>&nbsp;，否则返回 <code>false</code>。</p>\n",
    "\n",
    "<p>如果满足以下条件，则称一个单词 <code>w</code>&nbsp;比另一个单词 <code>z</code>&nbsp;<strong>严格大</strong>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>w</code> 在&nbsp;<strong>字典序上大于</strong> <code>z</code>。</li>\n",
    "\t<li>如果 <code>w<sub>1</sub></code> 是 <code>w</code> 的第一个字母，<code>z<sub>1</sub></code> 是 <code>z</code> 的第一个字母，那么 <code>w<sub>1</sub></code> 应该 <strong>等于</strong> <code>z<sub>1</sub></code> 或者是字母表中 <code>z<sub>1</sub></code> <strong>后面相邻&nbsp;</strong>的字母。</li>\n",
    "\t<li>例如，单词 <code>\"care\"</code>&nbsp;比&nbsp;<code>\"book\"</code> 和 <code>\"car\"</code>&nbsp;严格大，但不比&nbsp;<code>\"ant\"</code> 或 <code>\"cook\"</code>&nbsp;严格大。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果在 <code>s</code> 和 <code>t</code> 不同的第一个位置处，字符串 <code>s</code>&nbsp;的字母比字符串 <code>t</code>&nbsp;的字母在字母表中的顺序更靠后，则称为字符串 <code>s</code> 在 <strong>字典序上大于</strong> 字符串 <code>t</code>。如果前 <code>min(s.length, t.length)</code> 个字符没有区别，那么较长的字符串是在字典序上较大的那一个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> a = [\"avokado\",\"dabar\"], b = [\"brazil\"]\n",
    "\n",
    "<strong>输出:</strong> false\n",
    "\n",
    "<strong>解释:</strong> Alice 必须从单词 \"avokado\" 来开始游戏，因为这是她最小的单词，然后 Bob 使用他唯一的单词 \"brazil\"，他可以使用它因为它的第一个字母 'b' 在 Alice 的单词的第一个字母 'a' 之后。\n",
    "\n",
    "Alice 无法出牌，因为剩下的唯一单词的第一个字母既不等于 'b' 也不是 'b' 之后的字母 'c'。\n",
    "\n",
    "所以，Alice 输了，游戏结束。</pre>\n",
    "<strong>示例 2：</strong>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> a = [\"ananas\",\"atlas\",\"banana\"], b = [\"albatros\",\"cikla\",\"nogomet\"]\n",
    "\n",
    "<strong>输出:</strong> true\n",
    "\n",
    "<strong>解释:</strong> Alice 必须从单词 \"ananas\" 来开始游戏。\n",
    "\n",
    "Bob 无法出牌，因为他唯一拥有的以字母 'a' 或 'b' 开头的单词是 \"albatros\"，而它比 Alice 的单词小。\n",
    "\n",
    "所以，Alice 获胜，游戏结束。</pre>\n",
    "<strong>示例 3：</strong>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> a = [\"hrvatska\",\"zastava\"], b = [\"bijeli\",\"galeb\"]\n",
    "\n",
    "<strong>输出:</strong> true\n",
    "\n",
    "<strong>解释:</strong> Alice 必须从单词 \"hrvatska\" 来开始游戏。\n",
    "\n",
    "Bob 无法出牌，因为他的两个单词的第一个字母都比 Alice 的单词的第一个字母 'h' 小。\n",
    "\n",
    "所以，Alice 获胜，游戏结束。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>约束条件：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= a.length, b.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>a[i]</code> 和 <code>b[i]</code> 仅包含小写英文字母。</li>\n",
    "\t<li><code>a</code> 和 <code>b</code> 按 <strong>字典序排序</strong>。</li>\n",
    "\t<li><code>a</code> 和 <code>b</code> 中所有的单词都是&nbsp;<strong>不同的</strong>。</li>\n",
    "\t<li><code>a</code> 和 <code>b</code> 中所有单词的长度之和不超过 <code>10<sup>6</sup></code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-wording-game](https://leetcode.cn/problems/the-wording-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-wording-game](https://leetcode.cn/problems/the-wording-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"avokado\",\"dabar\"]\\n[\"brazil\"]', '[\"ananas\",\"atlas\",\"banana\"]\\n[\"albatros\",\"cikla\",\"nogomet\"]', '[\"hrvatska\",\"zastava\"]\\n[\"bijeli\",\"galeb\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        def alicePlay() -> bool:\n",
    "            nonlocal alicePtr, pre\n",
    "            while alicePtr < len(a):\n",
    "                cur = a[alicePtr]\n",
    "                alicePtr += 1\n",
    "                if (cur[0] == pre[0] and cur > pre) or (ord(cur[0]) == ord(pre[0]) + 1):\n",
    "                    pre = cur\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        def bobPlay() -> bool:\n",
    "            nonlocal bobPtr, pre\n",
    "            while bobPtr < len(b):\n",
    "                cur = b[bobPtr]\n",
    "                bobPtr += 1\n",
    "                if (cur[0] == pre[0] and cur > pre) or (ord(cur[0]) == ord(pre[0]) + 1):\n",
    "                    pre = cur\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        alicePtr = 1\n",
    "        bobPtr = 0\n",
    "        pre = a[0]\n",
    "        while True:\n",
    "            if not bobPlay():\n",
    "                return True\n",
    "            if not alicePlay():\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "\n",
    "        pa = 1\n",
    "        pb = 0\n",
    "        cur = 1\n",
    "        last = a[0]\n",
    "        \n",
    "        while True:\n",
    "            if cur:\n",
    "                if pb==len(b): return True\n",
    "                if (b[pb][0]==last[0] and b[pb]>last) or ord(b[pb][0])-ord(last[0])==1:\n",
    "                    last=b[pb]\n",
    "                    cur^=1\n",
    "                pb+=1\n",
    "            else:\n",
    "                if pa==len(a): return False\n",
    "                if (a[pa][0]==last[0] and a[pa]>last) or ord(a[pa][0])-ord(last[0])==1:\n",
    "                    last=a[pa]\n",
    "                    cur^=1\n",
    "                pa+=1\n",
    "        \n",
    "        return cur==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        i, j, k = 1, 0, 1\n",
    "        w = a[0]\n",
    "        while 1:\n",
    "            if k:\n",
    "                if j == len(b):\n",
    "                    return True\n",
    "                if (b[j][0] == w[0] and b[j] > w) or ord(b[j][0]) - ord(w[0]) == 1:\n",
    "                    w = b[j]\n",
    "                    k ^= 1\n",
    "                j += 1\n",
    "            else:\n",
    "                if i == len(a):\n",
    "                    return False\n",
    "                if (a[i][0] == w[0] and a[i] > w) or ord(a[i][0]) - ord(w[0]) == 1:\n",
    "                    w = a[i]\n",
    "                    k ^= 1\n",
    "                i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "\n",
    "        pa = 1\n",
    "        pb = 0\n",
    "        cur = 1\n",
    "        last = a[0]\n",
    "        \n",
    "        while True:\n",
    "            if cur:\n",
    "                if pb==len(b): return True\n",
    "                if (b[pb][0]==last[0] and b[pb]>last) or ord(b[pb][0])-ord(last[0])==1:\n",
    "                    last=b[pb]\n",
    "                    cur^=1\n",
    "                pb+=1\n",
    "            else:\n",
    "                if pa==len(a): return False\n",
    "                if (a[pa][0]==last[0] and a[pa]>last) or ord(a[pa][0])-ord(last[0])==1:\n",
    "                    last=a[pa]\n",
    "                    cur^=1\n",
    "                pa+=1\n",
    "        \n",
    "        return cur==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        alice = ['' for _ in range(26)]\n",
    "        bob = ['' for _ in range(26)]\n",
    "        for c in a:\n",
    "            alice[ord(c[0]) - ord('a')] = max(alice[ord(c[0]) - ord('a')],c)\n",
    "        for c in b:\n",
    "            bob[ord(c[0]) - ord('a')] = max(bob[ord(c[0]) - ord('a')],c)\n",
    "        cur = sorted(a)[0]\n",
    "        f = 1\n",
    "        while True:\n",
    "            if f:\n",
    "                # bob\n",
    "                tmp = ord(cur[0]) - ord('a')\n",
    "                if bob[tmp] > cur:\n",
    "                    cur = bob[tmp]\n",
    "                elif tmp + 1 >= 26 or bob[tmp + 1] == '':\n",
    "                    return True\n",
    "                else:\n",
    "                    cur = bob[tmp + 1]\n",
    "            else:\n",
    "                # alice\n",
    "                tmp = ord(cur[0]) - ord('a')\n",
    "                if alice[tmp] > cur:\n",
    "                    cur = alice[tmp]\n",
    "                elif tmp + 1 >= 26 or alice[tmp + 1] == '':\n",
    "                    return False\n",
    "                else:\n",
    "                    cur = alice[tmp + 1]\n",
    "            f ^= 1 \n",
    "        return True\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        s = {}\n",
    "        t = {}\n",
    "        for j in a:\n",
    "            s[j[0]] = j \n",
    "        for j in b:\n",
    "            t[j[0]] = j \n",
    "        c = a[0]\n",
    "        @cache \n",
    "        def f(ix, pre): \n",
    "            i = ord(pre[0])\n",
    "            j = chr(i)\n",
    "            k = chr(i+1)\n",
    "            if ix==1:\n",
    "                a1 = True \n",
    "                a2 = True \n",
    "                if j in t:\n",
    "                    if t[j]>pre:\n",
    "                        a1 = f(0, t[j])\n",
    "                if k in t:\n",
    "                    a2 = f(0, t[k])\n",
    "                return a1 and a2 \n",
    "            else:\n",
    "                a1 = False \n",
    "                a2 = False  \n",
    "                if j in s:\n",
    "                    if s[j] > pre:\n",
    "                        a1 = f(1, s[j])\n",
    "                if k in s:\n",
    "                    a2 = f(1, s[k])\n",
    "                return a1 or a2 \n",
    "        return f(1, c)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        ad = defaultdict(list)\n",
    "        bd = defaultdict(list)\n",
    "        win_a = defaultdict(list)\n",
    "        win_b = defaultdict(list)\n",
    "        for word in a:\n",
    "            ad[word[0]].append(word)\n",
    "        for word in b:\n",
    "            bd[word[0]].append(word)\n",
    "        for i in range(122, 96, -1):\n",
    "            cur_letter = chr(i)\n",
    "            nxt_letter = chr(i + 1)\n",
    "            a_list = ad[cur_letter]\n",
    "            b_list = bd[cur_letter]\n",
    "            if len(a_list) > 0 and len(b_list) > 0:\n",
    "                win_a[cur_letter] = [0] * len(a_list)\n",
    "                win_b[cur_letter] = [0] * len(b_list)\n",
    "                nxt_a = max(win_a[nxt_letter] + [0])\n",
    "                nxt_b = max(win_b[nxt_letter] + [0])\n",
    "                cur_a = cur_b = 0\n",
    "                a_index = len(a_list) - 1\n",
    "                b_index = len(b_list) - 1\n",
    "                while a_index > -1 or b_index > -1:\n",
    "                    if a_index < 0 or (b_index > -1 and a_list[a_index] < b_list[b_index]):\n",
    "                        cur_index = b_index\n",
    "                        ab_flag = 1\n",
    "                        b_index -= 1\n",
    "                    else:\n",
    "                        cur_index = a_index\n",
    "                        ab_flag = 0\n",
    "                        a_index -= 1\n",
    "                    if ab_flag == 0:\n",
    "                        if max(nxt_b, cur_b) == 0:\n",
    "                            win_a[cur_letter][cur_index] = 1\n",
    "                            cur_a = 1\n",
    "                    else:\n",
    "                        if max(nxt_a, cur_a) == 0:\n",
    "                            win_b[cur_letter][cur_index] = 1\n",
    "                            cur_b = 1\n",
    "            elif len(a_list) > 0:\n",
    "                nxt_b = max(win_b[nxt_letter] + [0])\n",
    "                if nxt_b == 1:\n",
    "                    win_a[cur_letter] = [0] * len(a_list)\n",
    "                else:\n",
    "                    win_a[cur_letter] = [1] * len(a_list)\n",
    "            elif len(b_list) > 0:\n",
    "                nxt_a = max(win_a[nxt_letter] + [0])\n",
    "                if nxt_a == 1:\n",
    "                    win_b[cur_letter] = [0] * len(b_list)\n",
    "                else:\n",
    "                    win_b[cur_letter] = [1] * len(b_list)\n",
    "            else:\n",
    "                continue\n",
    "        return win_a[a[0][0]][0] == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "\n",
    "        a.append('0')\n",
    "        b.append('0')\n",
    "        posa = {}\n",
    "        posb = {}\n",
    "\n",
    "        for j in range(1,len(a)):\n",
    "            if a[j][0]!=a[j-1][0]:\n",
    "                posa[a[j-1][0]]=j-1\n",
    "        \n",
    "        for j in range(1,len(b)):\n",
    "            if b[j][0]!=b[j-1][0]:\n",
    "                posb[b[j-1][0]]=j-1      \n",
    "\n",
    "        @cache\n",
    "        def dfs(who,last):\n",
    "            tgt = ord(last[0])\n",
    "            if who==0:\n",
    "                cur = chr(tgt)\n",
    "                if cur in posa and a[posa[cur]]>last and not dfs(who^1,a[posa[cur]]):\n",
    "                    return True\n",
    "                cur = chr(tgt+1)\n",
    "                if cur in posa and not dfs(who^1,a[posa[cur]]):\n",
    "                    return True\n",
    "            else:\n",
    "                cur = chr(tgt)\n",
    "                # print(who,last,tgt,cur)\n",
    "                if cur in posb and b[posb[cur]]>last and not dfs(who^1,b[posb[cur]]):\n",
    "                    return True\n",
    "                cur = chr(tgt+1)\n",
    "                # print(who,last,cur)\n",
    "                if cur in posb and not dfs(who^1,b[posb[cur]]):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return not dfs(1,a[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "\n",
    "        lst = [[w, 0] for w in a] + [[w, 1] for w in b]\n",
    "        lst.sort()\n",
    "        m = len(lst)\n",
    "        dct = [[] for _ in range(m)]\n",
    "        post = [defaultdict(list), defaultdict(list)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            s, ind = lst[i]\n",
    "            dct[i].extend(post[1-ind][s[0]][:1]+post[1-ind][s[0]][-1:])\n",
    "            x = chr(ord(s[0])+1)\n",
    "            if x <= \"z\":\n",
    "                dct[i].extend(post[1 - ind][x][:1]+post[1 - ind][x][-1:])\n",
    "            post[ind][s[0]].append(i)\n",
    "        \n",
    "        dp = [0]*m\n",
    "        post = [[0]*(m+1) for _ in range(2)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            s, ind = lst[i]\n",
    "            if not dct[i]:\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                dct[i].sort()\n",
    "                a, b = dct[i][0], dct[i][-1]\n",
    "                if post[1-ind][a] - post[1-ind][b+1] == 0:\n",
    "                    dp[i] = 1\n",
    "            post[ind][i] = post[ind][i + 1] + dp[i]\n",
    "            post[1 - ind][i] = post[1 - ind][i + 1]\n",
    "        for i in range(m):\n",
    "            if lst[i][1] == 0:\n",
    "                return dp[i] == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "\n",
    "        lst = [[w, 0, i] for i, w in enumerate(a)] + [[w, 1, i] for i, w in enumerate(b)]\n",
    "        lst.sort()\n",
    "        dct = [defaultdict(list) for _ in range(2)]\n",
    "        post = [defaultdict(list), defaultdict(list)]\n",
    "        m = len(lst)\n",
    "        for i in range(m-1, -1, -1):\n",
    "            s, ind, j = lst[i]\n",
    "            dct[ind][j].extend(post[1-ind][s[0]][:2])\n",
    "            x = chr(ord(s[0])+1)\n",
    "            if x <= \"z\":\n",
    "                dct[ind][j].extend(post[1 - ind][x][:2])\n",
    "\n",
    "            post[ind][s[0]].append(j)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(ind_, pre):\n",
    "            for w in dct[ind_][pre]:\n",
    "                if dfs(1-ind_, w):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        def can_win(cur_idx, cur_turn):\n",
    "          if cur_turn == 'a':\n",
    "              cur_start = a[cur_idx]\n",
    "              cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "              idx1 = bisect_left(b, cur_start, )\n",
    "              idx2 = bisect_left(b, cur_start2, )\n",
    "              for i in range(idx1, min(idx2, idx1+1)):\n",
    "                  ret1 = can_win(i, 'b')\n",
    "                  if ret1:\n",
    "                      return False\n",
    "              return True\n",
    "          else:\n",
    "              cur_start = b[cur_idx]\n",
    "              cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "              idx1 = bisect_left(a, cur_start, )\n",
    "              idx2 = bisect_left(a, cur_start2, )\n",
    "              for i in range(idx1, min(idx2, idx1+1)):\n",
    "                  ret1 = can_win(i, 'a')\n",
    "                  if ret1:\n",
    "                      return False\n",
    "              return True\n",
    "        return can_win(0, 'a')\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        ab = [a,b]\n",
    "        @cache\n",
    "        def dp(turn,idx):\n",
    "            if idx>=len(ab[turn]):\n",
    "                return False\n",
    "            w = ab[turn][idx]\n",
    "            w2 = chr(ord(w[0])+2)\n",
    "            i1 = bisect.bisect_left(ab[1-turn],w)\n",
    "            i2 = bisect.bisect_left(ab[1-turn],w2)\n",
    "            if i1>=i2:\n",
    "                return True\n",
    "            return not dp(1-turn,i1)\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        ab = [a,b]\n",
    "        @cache\n",
    "        def dp(turn,idx):\n",
    "            if idx>=len(ab[turn]):\n",
    "                return False\n",
    "            w = ab[turn][idx]\n",
    "            w2 = chr(ord(w[0])+2)\n",
    "            i1 = bisect.bisect_left(ab[1-turn],w)\n",
    "            i2 = bisect.bisect_left(ab[1-turn],w2)\n",
    "            for i in range(i1,min(i1+1,i2)):\n",
    "                if dp(1-turn,i):\n",
    "                    return False\n",
    "            return True\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "      @cache\n",
    "      def can_win(cur_idx, cur_turn):\n",
    "          if cur_turn == 'a':\n",
    "              cur_start = a[cur_idx]\n",
    "              cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "              idx1 = bisect_left(b, cur_start, )\n",
    "              idx2 = bisect_left(b, cur_start2, )\n",
    "              for i in range(idx1, min(idx2, idx1+1)):\n",
    "                  ret1 = can_win(i, 'b')\n",
    "                  if ret1:\n",
    "                      return False\n",
    "              return True\n",
    "          else:\n",
    "              cur_start = b[cur_idx]\n",
    "              cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "              idx1 = bisect_left(a, cur_start, )\n",
    "              idx2 = bisect_left(a, cur_start2, )\n",
    "              for i in range(idx1, min(idx2, idx1+1)):\n",
    "                  ret1 = can_win(i, 'a')\n",
    "                  if ret1:\n",
    "                      return False\n",
    "              return True\n",
    "      return can_win(0, 'a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "from sortedcontainers import SortedList\n",
    "from functools import lru_cache\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        \"\"\"\n",
    "        :param a:\n",
    "        :param b:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def can_win(cur_idx, cur_turn):\n",
    "            if cur_turn == 'a':\n",
    "                cur_start = a[cur_idx]\n",
    "                cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "                idx1 = bisect_left(b, cur_start, )\n",
    "                idx2 = bisect_left(b, cur_start2, )\n",
    "                for i in range(idx1, min(idx2, idx1+1)):\n",
    "                    ret1 = can_win(i, 'b')\n",
    "                    if ret1:\n",
    "                        return False\n",
    "                return True\n",
    "            else:\n",
    "                cur_start = b[cur_idx]\n",
    "                cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "                idx1 = bisect_left(a, cur_start, )\n",
    "                idx2 = bisect_left(a, cur_start2, )\n",
    "                for i in range(idx1, min(idx2, idx1+1)):\n",
    "                    ret1 = can_win(i, 'a')\n",
    "                    if ret1:\n",
    "                        return False\n",
    "                return True\n",
    "        return can_win(0, 'a')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "from sortedcontainers import SortedList\n",
    "from functools import lru_cache\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param a:\n",
    "        :param b:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def can_win(cur_idx, cur_turn):\n",
    "            if cur_turn == 'a':\n",
    "                cur_start = a[cur_idx]\n",
    "                cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "                idx1 = bisect_left(b, cur_start, )\n",
    "                idx2 = bisect_left(b, cur_start2, )\n",
    "                for i in range(idx1, min(idx2, idx1+1)):\n",
    "                    ret1 = can_win(i, 'b')\n",
    "                    if ret1:\n",
    "                        return False\n",
    "                return True\n",
    "            else:\n",
    "                cur_start = b[cur_idx]\n",
    "                cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "                idx1 = bisect_left(a, cur_start, )\n",
    "                idx2 = bisect_left(a, cur_start2, )\n",
    "                for i in range(idx1, min(idx2, idx1+1)):\n",
    "                    ret1 = can_win(i, 'a')\n",
    "                    if ret1:\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "\n",
    "        return can_win(0, 'a')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "from sortedcontainers import SortedList\n",
    "from functools import lru_cache\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "  def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "      \"\"\"\n",
    "      :param a:\n",
    "      :param b:\n",
    "      :return:\n",
    "      \"\"\"\n",
    "      @lru_cache(None)\n",
    "      def can_win(cur_idx, cur_turn):\n",
    "          if cur_turn == 'a':\n",
    "              cur_start = a[cur_idx]\n",
    "              cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "              idx1 = bisect_left(b, cur_start, )\n",
    "              idx2 = bisect_left(b, cur_start2, )\n",
    "              for i in range(idx1, min(idx2, idx1+1)):\n",
    "                  ret1 = can_win(i, 'b')\n",
    "                  if ret1:\n",
    "                      return False\n",
    "              return True\n",
    "          else:\n",
    "              cur_start = b[cur_idx]\n",
    "              cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "              idx1 = bisect_left(a, cur_start, )\n",
    "              idx2 = bisect_left(a, cur_start2, )\n",
    "              for i in range(idx1, min(idx2, idx1+1)):\n",
    "                  ret1 = can_win(i, 'a')\n",
    "                  if ret1:\n",
    "                      return False\n",
    "              return True\n",
    "      return can_win(0, 'a')\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "from sortedcontainers import SortedList\n",
    "from functools import lru_cache\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "    def canAliceWin(self, a: List[str], b: List[str]) -> bool:\n",
    "        \"\"\"\n",
    "        :param a:\n",
    "        :param b:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def can_win(cur_idx, cur_turn):\n",
    "            if cur_turn == 'a':\n",
    "                cur_start = a[cur_idx]\n",
    "                cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "                idx1 = bisect_left(b, cur_start, )\n",
    "                idx2 = bisect_left(b, cur_start2, )\n",
    "                for i in range(idx1, min(idx2, idx1+1)):\n",
    "                    ret1 = can_win(i, 'b')\n",
    "                    if ret1:\n",
    "                        return False\n",
    "                return True\n",
    "            else:\n",
    "                cur_start = b[cur_idx]\n",
    "                cur_start2 = chr(ord(cur_start[0]) + 2)\n",
    "                idx1 = bisect_left(a, cur_start, )\n",
    "                idx2 = bisect_left(a, cur_start2, )\n",
    "                for i in range(idx1, min(idx2, idx1+1)):\n",
    "                    ret1 = can_win(i, 'a')\n",
    "                    if ret1:\n",
    "                        return False\n",
    "                return True\n",
    "        return can_win(0, 'a')\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
